package solution;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-03-11
 * Time: 21:30
 */
class Solution2 {
    int[] X = {-1, 1, 0, 0};
    int[] Y = {0, 0, -1, 1};

    public int maxAreaOfIsland(int[][] grid) {
        int num = 0;
        int row = grid.length;
        int col = grid[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                num = Math.max(dfs(grid, i, j), num);
            }
        }
        return num;
    }

    public int dfs(int[][] grid, int x, int y) {
        int row = grid.length;
        int col = grid[0].length;
        if (x < 0 || x >= row || y < 0 || y >= col || grid[x][y] == 0) {
            return 0;
        }
        grid[x][y] = 0;
        int ans = 1;
        for (int i = 0; i < 4; i++) {
            int dx = x + X[i];
            int dy = y + Y[i];
            ans += dfs(grid, dx, dy);
        }
        return ans;
    }
}


//class Solution {
//    int[] X = {-1, 1, 0, 0};
//    int[] Y = {0, 0, -1, 1};
//
//    public int maxAreaOfIsland(int[][] grid) {
//        int num = 0;
//        int row = grid.length;
//        int col = grid[0].length;
//        Deque<int[]> queue = new LinkedList<>();
//        for (int i = 0; i < row; i++) {
//            for (int j = 0; j < col; j++) {
//                int cur = 0;
//                queue.offer(new int[]{i, j});
//                while (!queue.isEmpty()) {
//                    int[] temp = queue.poll();
//                    int x = temp[0];
//                    int y = temp[1];
//                    if (x < 0 || x >= row || y < 0 || y >= col || grid[x][y] == 0) {
//                        continue;
//                    }
//                    cur++;
//                    grid[x][y] = 0;
//                    for (int k = 0; k < 4; k++) {
//                        int dx = x + X[k];
//                        int dy = y + Y[k];
//                        queue.offer(new int[]{dx, dy});
//                    }
//                }
//                num = Math.max(num, cur);
//            }
//        }
//        return num;
//    }
//}


